class Solution:
	# @param triangle, a list of lists of integers
	# @return an integer
	def minimumTotal(self, triangle):
		size = len(triangle)
		if size <= 0:
			return 0
		short = [[],[]]
		short[(size+1)%2] = [triangle[size-1][x] for x in xrange(size)]
		short[(size)%2] = [0 for x in xrange(size)]
		for i in xrange(size-2,-1,-1):
			for j in xrange(i+1):
				short[i%2][j] = triangle[i][j] + min(short[(i+1)%2][j], short[(i+1)%2][j+1])
				
		return short[0][0]


if __name__ == '__main__':
	so = Solution()
	t = [
	     [2],
	    [3,4],
	   [1,5,7],
	  [4,9,8,1]
	]
	print so.minimumTotal(t)